package 剑指offer;


/*
 * Author：江松
 * Date：2023/3/14 20:19
 *
 数组中只出现一次的数字:哈希表
 ***位运算:0^n=n,x^n^n=x;
 用0依次位运算后的结果就是2个只出现1次数的异或结果，
 异或结果某位为1说明，在该位2数不同，因此以第一个1的位置分组，
 这样相同的数肯定在一个分组中，依次异或即可得出2个分组中原来的数
 */

import java.util.HashMap;

public class Main26 {
    //位运算
    public void FindNumsAppearOnce2(int [] array,int num1[] , int num2[]) {
        int xor=0;
        for(int i:array){
            xor^=i;
        }
        //第几位不同
        int bit=0;
        while((xor&(1<<bit))==0){
            bit++;
        }
        System.out.println("xor:"+xor);
        System.out.println("bit:"+bit);
        for(int i:array){
            if((i&(1<<bit))==0){
                num1[0]^=i;
                System.out.println("第一组:"+i);
            }else{
                num2[0]^=i;
                System.out.println("第二组："+i);
            }
        }
    }
    //哈希表
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        HashMap<Integer,Integer>map=new HashMap<>();
        for(int i:array){
            if(!map.containsKey(i)){
                map.put(i,1);
            }else{
                map.put(i,map.get(i)+1);
            }
        }
        boolean flag=false;
        for(int i=0;i<array.length;++i){
            if(map.get(array[i])==1){
                if(!flag){
                    num1[0]=i;
                    flag=true;
                }
                else num2[0]=i;
            }
        }
    }
    public static void main(String[] args) {
        int arr[]={3,4,4,5,6,6};
        int num1[]=new int[1];
        int num2[]=new int[1];
        new Main26().FindNumsAppearOnce2(arr,num1,num2);
    }
}
